#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;

struct AREA{
    int left;
    int right;
};

struct line{
    int next;
    char cost;
    line(){
        next=0;
        cost=' ';
    }
    line(int n, char c){
        next=n;
        cost=c;
    }
};
struct node{
    int id;
    vector<line> edge;
    node(){
        id=0;
    }
    node(int n){
        id=n;
    }
};

struct minimum_node{
    int id;
    set<int> set;
    minimum_node(int n){
        id=n;
    }
};

const char EPSILON = '@';
char token = NULL; // 当前获取的字符
string reg;   // 用户输入的正则表达式
int index=-1;  // token 所在下标
int NODE_NUM = 0;   // 有向图中结点数量
vector<node> graph;  // 存储的有向图
vector< vector< set<int> > > table;      //NFA转换表
set<char>table_head;                     // 表头
set<int> td;

void getToken(){
    token=reg[++index];
}

char getAheadToken(){
    return reg[index-1];
}
void error(){cout<<"error"<<endl;}


AREA re(); // 或运算
AREA rt(); // 连接运算
AREA rf(); // 闭包
AREA rn(); // 括号/单个字符

void match(char expectedToken){
    if(token==expectedToken)
        getToken();
    else error();
}

AREA re(){
    AREA temp;
    temp = rt();
    while(token=='|'){
        match(token);
        // 新增两个结点
        node j = node(NODE_NUM++);
        graph.push_back(j);
        node k = node(NODE_NUM++);
        graph.push_back(k);
        // 连接上面两条边
        graph[j.id].edge.push_back(line(temp.left,EPSILON));
        graph[temp.right].edge.push_back(line(k.id,EPSILON));
        // 获取另外一个选项的范围
        AREA t = rt();
        // 连接下面两条边
        graph[j.id].edge.push_back(line(t.left,EPSILON));
        graph[t.right].edge.push_back(line(k.id,EPSILON));
        // 调整temp的范围
        temp.left = j.id;
        temp.right = k.id;
    }
    return temp;
}

AREA rt(){
    AREA temp;
    temp = rf();
    while(isalpha(token)|| token=='('){
        AREA f = rf();
        graph[temp.right].edge.push_back(line(f.left,EPSILON));
        temp.right = f.right;
    };
    return temp;
}

AREA rf(){
    AREA temp;
    temp = rn();
    while(token=='*'){
        match(token);
        graph[temp.right].edge.push_back(line(temp.left,EPSILON));
        // 新增两个结点
        node j = node(NODE_NUM++);
        graph.push_back(j);
        node k = node(NODE_NUM++);
        graph.push_back(k);
        // 添加与这两个结点相关的连线
        graph[j.id].edge.push_back(line(temp.left,EPSILON));
        graph[j.id].edge.push_back(line(k.id,EPSILON));
        graph[temp.right].edge.push_back(line(k.id,EPSILON));
        // 调整temp范围
        temp.left = j.id;
        temp.right = k.id;
    }
    return temp;
}

AREA rn(){
    AREA temp;
    if(token=='('){
        match('(');
        temp = re();
        match(')');
    }
    else if (isalpha(token)){
        match(token);
        node j = node(NODE_NUM++);
        graph.push_back(j);
        node k = node(NODE_NUM++);
        graph.push_back(k);
        graph[j.id].edge.push_back(line(k.id,getAheadToken()));
        temp.left = j.id;
        temp.right = k.id;
        table_head.insert(getAheadToken());
    }
    return temp;
}

// 打印-NFA
void NFA_print(const vector<node>& graph){
    for(int i=0;i<graph.size();i++){
        cout<<i<<':';
        for(int j=0;j<graph[i].edge.size();j++){
            cout<<graph[i].edge[j].cost<<"->"<<graph[i].edge[j].next<<' ';
        }
        cout<<endl;
    }
}

// 打印-DFA中间版本的td
void td_print(const set<int>& a){
    if(a.size()==0){
        cout<<EPSILON;
        return;
    }
    set<int>::iterator it;
    for(it=a.begin();it!=a.end();it++){
        cout<<*it<<' ';
    }
}

// 打印-DFA中间版本的整个表格
void table_print(const vector< vector< set<int> > >& table){
    for(int i=0;i<table.size();i++){
        for(int j=0;j<table[i].size();j++){
            cout<<'{';
            td_print(table[i][j]);
            cout<<'}';
            cout<<'\t';
        }
        cout<<endl;
    }
}

// 打印-DFA-简洁版本，单个数字标识
void DFA_print(const vector< vector<int> >& a){
    set<char>::iterator it;
    cout<<"  ";
    for(it=table_head.begin();it!=table_head.end();it++)
        cout<<*it<<' ';
    cout<<endl;

    for(int i=0;i<a.size();i++){
        for(int j=0;j<a[i].size();j++){
          a[i][j]!=-1?cout<<a[i][j]<<' ':cout<<EPSILON<<' ';
        }
        cout<<endl;
    }
}

// 打印-DFA最小化之后的集合分类
void s_print(vector<minimum_node>& s){
    for(int i=0;i<s.size();i++){
        set<int>::iterator it;
        cout<<i<<":{";
        for(it=s[i].set.begin();it!=s[i].set.end();it++){
            cout<<*it<<',';
        }
        cout<<'}'<<endl;
    }
}

// 打印-最小化的DFA
void minimum_dfa_print(const vector< vector<int> >& a){
    set<char>::iterator it;
    cout<<"  ";
    for(it=table_head.begin();it!=table_head.end();it++)
        cout<<*it<<' ';
    cout<<endl;

    for(int i=0;i<a.size();i++){
        for(int j=0;j<a[i].size();j++){
            a[i][j]==-1?cout<<EPSILON<<' ':cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }
}

// 打印-经过的字符集
void head_print(const set<char>& a){
    set<char>::iterator it;
    cout<<"\t\t";
    for(it=a.begin();it!=a.end();it++)
        cout<<*it<<'\t';
    cout<<endl;
}


// 求从某个点出发的允许某个allowChar的EPSILON闭包
void walk(int index,char allowChar,bool flag){
    for(int i=0;i<graph[index].edge.size();i++){
        if(!flag&&graph[index].edge[i].cost==allowChar){
            flag = true;
            td.insert(graph[index].edge[i].next);
            //td.insert(index);
            walk(graph[index].edge[i].next,allowChar,flag);
        }
        else if(flag&&graph[index].edge[i].cost==EPSILON){
            td.insert(graph[index].edge[i].next);
            //td.insert(index);
            walk(graph[index].edge[i].next,allowChar,flag);
        }
    }
}

// 判断两个集合是否一致
bool equalSet(const set<int>& a, const set<int>& b){
    if(a.size()!=b.size())return false;
    set<int>::iterator it_a,it_b;
    it_a = a.begin();
    it_b = b.begin();
    while(it_a!=a.end()){
        if(*it_a!=*it_b) return false;
        it_a++;
        it_b++;
    }
    return true;
}

// 在table中，单个td获取它实际对应的行号
int getRowsNum(const set<int>& a){
    for(int i=0;i<table.size();i++){
        if(equalSet(table[i][0],a)){
            return i;
        }
    }
    return -1;
}

// 判断集合a是否含有某个x元素
bool setHas(const set<int>& a, int x){
    set<int>::iterator it;
    for(it=a.begin();it!=a.end();it++){
        if(*it==x)return true;
    }
    return false;
}

// 最小化中将DFA中的状态分开不同集合下后，传入状态id返回集合id
int getSetNum(int state,const vector<minimum_node>& s){
    if(state==-1) return -1;
    for(int i=0;i<s.size();i++){
        if(setHas(s[i].set,state)){
            return i;
            break;
        }
    }
}

// 根据当前状态所处在的集合id，填到minimum表中
void fill_minimum(const vector< vector<int> >& dfa,vector< vector<int> >& minimum,const vector<int>& dict){
    if(dfa.size()!=minimum.size() || dfa[0].size()!=minimum[0].size()) return;
    for(int i=0;i<dfa.size();i++){
        for(int j=1;j<dfa[i].size();j++){
            minimum[i][j] = dfa[i][j]<0? -1:dict[dfa[i][j]];
        }
    }
}

// 在最小化中。判断表中的两行是否一致
bool equalRow(const vector<int>& a, const vector<int>& b){
    if(a.size()!=b.size()) return false;
    for(int i=1;i<a.size();i++){ // 注意：忽略了第一列的内容
//        cout<<a[i]<<endl;
//        cout<<b[i]<<endl;
        if(a[i]!=b[i]) return false;
    }
    return true;
}

int main()
{
    cout<<"input a reg:";
    cin>>reg;
    // begin NFA
    getToken();
    AREA area = re();


    walk(area.left,EPSILON,false);
    td.insert(area.left);

    // begin NFA-->DFA
    int current_row=0,current_col=0; // 已经处理的行数
    int cols = 1+ table_head.size();
    set<char>::iterator it_th;

    // 初始化table[0][0]的闭包
    table.push_back(vector< set<int> >());
    table[0].resize(cols);
    table[0][0]=td;

    while(current_row<table.size()){
        current_col = 0;
        // begin form [0], walk all char in table_head
        for(it_th=table_head.begin();it_th!=table_head.end();it_th++){
            td.clear();
            // walk table[current_row][0]
            set<int>::iterator it_index;
            for(it_index=table[current_row][0].begin();it_index!=table[current_row][0].end();it_index++){
                walk(*it_index,*it_th,false);
            }
            table[current_row][++current_col]=td;
            if(td.size()>0){
                bool checked = true;
                // check new td is in rows
                for(int i=0;i<table.size();i++){
                    if(equalSet(table[i][0],td)){
                        checked = false;
                        break;
                    }
                }
                if(checked){
                    table.push_back(vector< set<int> >());
                    table.back().resize(cols);
                    table.back().front() = td;
                }
            }// end put new row

        }// end walk cols
        current_row++;

    }// end while

    vector< vector<int> > DFA(table.size(),vector<int>(cols,-1));

    for(int i=0;i<DFA.size();i++){
        DFA[i][0] = i;
        for(int j=1;j<cols;j++){
            if(table[i][j].size()>0){
                DFA[i][j] = getRowsNum(table[i][j]);
            }
        }
    }

    // begin 最小化
    int final_node = area.right; // 终态结点
    vector<int> dictionary(table.size()); // 用于记录每个状态到底在哪个集合下,s[状态id]=所在集合id
    vector<minimum_node> s; // 所有集合的汇总
    int current_sets = 0;
    s.push_back(minimum_node(0)); // 非终态
    s.push_back(minimum_node(1)); // 终态
    for(int i=0;i<table.size();i++){
        if(setHas(table[i][0],final_node)){
            s[1].set.insert(DFA[i][0]);
            dictionary[i] = 1;
        }
        else {
            s[0].set.insert(DFA[i][0]);
            dictionary[i] = 0;
        }
    }// 生成终态、非终态集合

    // 去空
    if(s.front().set.size()==0) s.erase(s.begin());
    if(s.back().set.size()==0) s.pop_back();

    vector< vector<int> >minimum(table.size(),vector<int>(cols,-1));// 记录dfa中每个状态经过每个字符转换后的集合id
    for(int i=0;i<minimum.size();i++){
        minimum[i][0] = i;
    }

    while(1){
        fill_minimum(DFA,minimum,dictionary); // 把最小化的表更新一下
        current_sets = s.size();
        for(int set_num=0;set_num<current_sets;set_num++){

            if(s[set_num].set.size()<=1) continue;

            minimum_node tmp_node = s[set_num];
            vector<int> candidate(0);
            set<int>::iterator it;
            candidate.push_back(set_num);
            s[set_num].set = set<int>();
            s[set_num].set.insert(*(tmp_node.set.begin()));

            for(it=tmp_node.set.begin();it!=tmp_node.set.end();it++){
                bool matchFlag=false; // 有没有从候选项中找到匹配的标志
                for(int j=0;j<candidate.size();j++){
                    set<int>::iterator it_first = s[candidate[j]].set.begin();
                    if(equalRow(minimum[*it_first],minimum[*it])){
                        if(dictionary[*it_first]!=dictionary[*it]){
                            dictionary[*it] = dictionary[*it_first];
                        }
                        s[candidate[j]].set.insert(*it);
                        matchFlag = true;
                        break;
                    }
                }

                if(!matchFlag){
                    int new_set = s.size();
                    candidate.push_back(new_set);
                    s.push_back(minimum_node(new_set));
                    s[new_set].set.insert(*it);
                }
            }
        }

        if(s.size()==current_sets) break;

    }// end while

    // 用于显示的最小化DFA
    vector< vector<int> > minimum_dfa(s.size(),vector<int>(cols,-1));
    for(int i=0;i<minimum_dfa.size();i++){
        minimum_dfa[i][0] = i;
        int represent = *(s[i].set.begin());
        for(int j=1;j<minimum_dfa[i].size();j++){
            minimum_dfa[i][j] = getSetNum(DFA[represent][j],s);
        }
    }

    cin.get();


    // UI部分
    char mode;
    bool mode_flag = true;
    cout<<"n:for print NFA"<<endl;
    cout<<"d:for print DFA"<<endl;
    cout<<"m:for print minimum DFA"<<endl;
    cout<<"q:for quit"<<endl;
    cout<<"tips:@ is for EPSILON"<<endl;

    while(mode_flag){
        cout<<"$ input your command:";
        cin>>mode;
        switch(mode){
            case 'n':
            case 'N':
                cout<<"--- show NFA ---"<<endl;
                NFA_print(graph);
                break;
            case 'd':
            case 'D':
                cout<<"--- show DFA middle version ---"<<endl;
                head_print(table_head);
                table_print(table);
                cout<<"--- show DFA ---"<<endl;
                DFA_print(DFA);
                break;
            case 'm':
            case 'M':
                cout<<"--- minimum ---"<<endl;
                minimum_dfa_print(minimum_dfa);
                break;
            default:mode_flag=false;
        }
    }
    return 0;
}

